#include "../include/dynamic_programming.h"
#include <string.h>

/**
 * 动态规划求解0-1背包问题
 * 时间复杂度：O(n*capacity)，空间复杂度：O(n*capacity)
 * @param items 物品数组
 * @param n 物品数量
 * @param capacity 背包容量
 * @param result 结果结构体指针
 */
void dynamic_programming_knapsack(Item* items, int n, int capacity, Result* result) {
    // 初始化结果
    result->total_value = 0;
    result->selected_count = 0;
    result->time_taken = 0;
    result->memory_used = 0;
    result->selected_items = NULL;

    // 记录开始时间
    clock_t start = clock();

    // 创建动态规划表
    double** dp = (double**)malloc((n + 1) * sizeof(double*));
    int** selected = (int**)malloc((n + 1) * sizeof(int*));
    if (!dp || !selected) {
        printf("Memory allocation failed\n");
        if (dp) free(dp);
        if (selected) free(selected);
        return;
    }

    // 初始化动态规划表
    for (int i = 0; i <= n; ++i) {
        dp[i] = (double*)calloc(capacity + 1, sizeof(double));
        selected[i] = (int*)calloc(capacity + 1, sizeof(int));
        if (!dp[i] || !selected[i]) {
            printf("Memory allocation failed\n");
            // 释放已分配的内存
            for (int j = 0; j < i; ++j) {
                free(dp[j]);
                free(selected[j]);
            }
            free(dp);
            free(selected);
            return;
        }
    }

    // 动态规划过程
    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= capacity; ++w) {
            if (items[i-1].weight <= w) {
                // 如果当前物品可以放入背包
                double value_with_item = dp[i-1][w - items[i-1].weight] + items[i-1].value;
                if (value_with_item > dp[i-1][w]) {
                    // 如果放入当前物品能获得更高的价值
                    dp[i][w] = value_with_item;
                    selected[i][w] = 1;
                } else {
                    // 否则保持不放当前物品
                    dp[i][w] = dp[i-1][w];
                    selected[i][w] = 0;
                }
            } else {
                // 如果当前物品不能放入背包
                dp[i][w] = dp[i-1][w];
                selected[i][w] = 0;
            }
        }
    }

    // 记录结束时间和内存使用
    clock_t end = clock();
    result->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;
    result->memory_used = (n + 1) * (capacity + 1) * (sizeof(double) + sizeof(int));

    // 保存结果
    result->total_value = dp[n][capacity];
    result->selected_items = (int*)malloc(n * sizeof(int));
    if (result->selected_items) {
        // 回溯找出选择的物品
        int w = capacity;
        for (int i = n; i > 0; --i) {
            if (selected[i][w]) {
                result->selected_items[result->selected_count++] = items[i-1].id;
                w -= items[i-1].weight;
            }
        }
    }

    // 释放内存
    for (int i = 0; i <= n; ++i) {
        free(dp[i]);
        free(selected[i]);
    }
    free(dp);
    free(selected);
} 